/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package roads_scholar;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * @author Seth Yost
 */
public class Roads_Scholar {

    /**
     * @param args the command line arguments
     */
    static int SIZE = 0;
    static int NUM_INTERSECTIONS = 0;
    static double distance[][] = null;
    static int predecessor[][] = null;
    static String[] name = null;
    static int num_signs = 0;
    
    //signs[from][to] = distance from from
    static double[][] signs = null;
    
    public static void main(String[] args) {
	// TODO code application logic here
	try {
	    FileReader fin = new FileReader("temp.txt");
	    BufferedReader in = new BufferedReader(fin);

	    FileWriter fout;
	
	    fout = new FileWriter("output.txt");
	    BufferedWriter out = new BufferedWriter(fout);

	    //intitializes the data recorded in the file
	    init(in);

	    //finds the best solution from anywhere to anywhere
	    double[][] solutions = Floyd_Warshall(distance);
	    
	    //from
	    for(int j = 0; j < name.length; j++)
	    {
		//to
		for(int k = 0; k < name.length; k++)
		{
		    if(name[j] != null && name[k] != null && j != k)
		    {
			int[] path = find_path(j, k);
			boolean correctPath = is_on_path(j, k, path);

			if(correctPath)
			{
			    //output the proper info
			    out.write("" + name[k]);
			    for(int a = name[k].length(); a < 20; a++)
			    {
				out.write(" ");
			    }
			    
			    //breaks on multiple signs
			    double distance = 0;
			    for(int m = 0; m < path.length; m++)
			    {
				distance += signs[j][path[m]];
			    }

			    if(solutions[j][k]%1 >= 0.5)
			    {
				int temp = (int)solutions[j][k]-(int)distance;
				out.write("" + temp+1 + "\n");
			    }
			    else
			    {
				int temp = (int)solutions[j][k]-(int)distance;
				out.write("" + temp + "\n");
			    }
			    out.flush();
			}
		    }
		}
	    }
	    
	} catch (IOException ex) {
	    Logger.getLogger(Roads_Scholar.class.getName()).log(Level.SEVERE, null, ex);
	}
	
    }
    
    public static double[][] Floyd_Warshall(double[][] weight)
    {
	int n = weight.length;
	double[][] best = weight;
	//best0 = weight;

	for(int k = 0; k < n; k++)
	{
	    for(int u = 0; u < n; u++)
	    {
		for(int v = 0; v < n; v++)
		{
                    //if (u != k)
		    {
			if((best[u][k] + best[k][v]) < best[u][v]) 
			{
			   best[u][v] = best[u][k] + best[k][v];
			   predecessor[u][v] = k;
			}
		    }
		}
	    }
	}
	return best;
    }

    //reads the input file and creates the appropriat structure
    public static void init(BufferedReader in)
    {
	String temp = null;
	try {
	    temp = in.readLine();
	    String[] temp_data = temp.split(" ");
	    int[] data = new int[temp_data.length];

	    for(int i = 0; i < temp_data.length; i++)
	    {
		data[i] = Integer.parseInt(temp_data[i]);
	    }

	    SIZE = data[0];
	    NUM_INTERSECTIONS = data[2];
	    distance = new double[SIZE][SIZE];
	    predecessor = new int[SIZE][SIZE];
	    name = new String[SIZE];
	    signs = new double[SIZE][SIZE];

	    //inits the data structurs
	    for(int i = 0; i < distance.length; i++)
	    {
		for(int j = 0; j < distance[i].length; j++)
		{
		    distance[i][j] = 999999999;		    
		    predecessor[i][j] = -1;
		}
		name[i] = null;
	    }
	    
	    //creates the roads from city to city and sets the distance and predicessor 
	    for(int m = 0; m < data[1]; m++)
	    {
		String temp2 = in.readLine();
		String[] temp_data2 = temp2.split(" ");
		double[] data2 = new double[temp_data2.length];
		for(int i = 0; i < temp_data.length; i++)
		{
		    data2[i] = Double.parseDouble(temp_data2[i]);
		}
		distance[(int)data2[0]][(int)data2[1]] = data2[2];
		distance[(int)data2[1]][(int)data2[0]] = data2[2];
		predecessor[(int)data2[0]][(int)data2[1]] = (int)data2[0];
		predecessor[(int)data2[1]][(int)data2[0]] = (int)data2[1];
		
	    }

	    //sets the cities with names
	    for(int k = 0; k < data[2]; k++)
	    {
		String temp2 = in.readLine();
		String[] temp_data2 = temp2.split(" ");
		name[Integer.parseInt(temp_data2[0])] = temp_data2[1];
	    }
	    
	    //number of signs on the map
	    num_signs = Integer.parseInt(in.readLine());
	    
	    //puts the info for each sign on the proper route
	    for(int s = 0; s < num_signs; s++)
	    {
		String temp2 = in.readLine();
		String[] temp_data2 = temp2.split(" ");
		double[] sign_data = new double[temp_data2.length];
		for(int i = 0; i < temp_data.length; i++)
		{
		    sign_data[i] = Double.parseDouble(temp_data2[i]);
		}
		signs[(int)sign_data[0]][(int)sign_data[1]] = sign_data[2];
	    }
	} 
	catch (IOException ex) 
	{
	    Logger.getLogger(Roads_Scholar.class.getName()).log(Level.SEVERE, null, ex);
	}
    }
    
    public static int[] find_path(int from, int to)
    {
	int[] path = new int[predecessor.length];
	int num_hops = 1;
	path[0] = to;
	while(predecessor[from][to] != from)
	{
	    path[num_hops] = predecessor[from][to];
	    num_hops++;
	    to = predecessor[from][to];
	}
	path[num_hops] = from;
	return path;
    }
    
    public static boolean is_on_path(int from, int to , int[] path)
    {
	for(int i = 0; i < path.length; i++)
	{
	    if(signs[from][path[i]] != 0.0)
	    {
		return true;
	    }
	}
	return false;	
    }
}
